package com.hxm.demo.newcoder;

import java.util.Stack;

public class TestBM1 {

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        ListNode listNode = ReverseList3(head);
        System.out.println(listNode);
    }

    public ListNode ReverseList1(ListNode head) {
        // write code here
        if (head == null) {
            return head;
        }
        ListNode newTail = new ListNode(head.val);
        ListNode newHead = null;
        while (head.next != null) {
            newHead = new ListNode(head.next.val);
            newHead.next = newTail;
            newTail = newHead;
            head = head.next;
        }
        return newTail;
    }

    public static ListNode ReverseList2(ListNode head) {
        // write code here
        if (head == null || head.next == null) {
            return head;
        }
        ListNode newHead = null;
        while (head != null) {
            ListNode temp = head.next;
            head.next = newHead;
            newHead = head;
            head = temp;
        }
        return newHead;
    }

    public static ListNode ReverseList3(ListNode head) {
        // write code here
        if (head == null || head.next == null) {
            return head;
        }
        Stack<ListNode> stack = new Stack<>();
        while (head != null) {
            ListNode temp = head.next;
            head.next = null;
            stack.push(head);
            head = temp;
        }
        if (stack.empty()) {
            return head;
        }
        ListNode temp = stack.pop();
        ListNode newHead = temp;
        while (!stack.empty()) {
            temp.next = stack.pop();
            temp = temp.next;
        }
        return newHead;
    }
}

class ListNode {
    int val;
    ListNode next = null;

    public ListNode(int val) {
        this.val = val;
    }
}
